// From  http://www.mazeworks.com/mazegen/mazetut/index.htm

#include "Maze.h"

#include <stdlib.h>
#include <time.h> // random
#include <cassert>
#include <stack>


using namespace std;



CMaze::CMaze() : m_uiSizeX(0),
				m_uiSizeY(0)
{
	srand(static_cast<unsigned int>(time(0)));
}

CMaze::~CMaze()
{
	reset();
}

void CMaze::generate(unsigned int uiSizeX, unsigned int uiSizeY)
{
	// reset map
	reset(uiSizeX, uiSizeY);
	// create a CellStack (LIFO) to hold a list of cell locations  
	std::stack<MazeCellPtr>	m_stkCells;
	// choose a cell at random and call it CurrentCell
	assert(m_uiSizeX != 0);
	assert(m_uiSizeY != 0);
	unsigned int uiCurrX = genRangedRndNb(0, m_uiSizeX - 1);
	unsigned int uiCurrY = genRangedRndNb(0, m_uiSizeY - 1);
	MazeCellPtr pCurrCell = m_vecCells[uiCurrY * m_uiSizeX + uiCurrX];
	// set TotalCells = number of cells in grid
	unsigned int uiTotalCells = m_vecCells.size();
	// set VisitedCells = 1  
	unsigned int uiVisitedCells = 1;

	while (uiVisitedCells < uiTotalCells)
	{
		std::vector<MazeCellPtr>	vecNeighbours;
		vecNeighbours.resize(CMaze::maxDirection);
		short					m_sNeighToVisit = 0;

		// find all neighbors of CurrentCell with all walls intact
		if (getNeighWithIntactWall(pCurrCell, vecNeighbours[CMaze::north], CMaze::north))
			m_sNeighToVisit |= SMazeCell::WallNorth;
		if (getNeighWithIntactWall(pCurrCell, vecNeighbours[CMaze::east], CMaze::east))
			m_sNeighToVisit |= SMazeCell::WallEast;
		if (getNeighWithIntactWall(pCurrCell, vecNeighbours[CMaze::south], CMaze::south))
			m_sNeighToVisit |= SMazeCell::WallSouth;
		if (getNeighWithIntactWall(pCurrCell, vecNeighbours[CMaze::west], CMaze::west))
			m_sNeighToVisit |= SMazeCell::WallWest;

		// if one or more found
		if (m_sNeighToVisit != 0)
		{
			unsigned int uiDirection = 0;
			MazeCellPtr pRndNeigh;

			// choose one at random  
			do 
			{
				uiDirection = genRangedRndNb(0, (CMaze::maxDirection - 1));
				if ( (1 << uiDirection) & m_sNeighToVisit )
				{
					pRndNeigh = vecNeighbours[uiDirection];
					break;
				}
			} while (true);
						
			// knock down the wall between it and CurrentCell  
			switch (uiDirection)
			{
			case CMaze::north:
				{
					pCurrCell->m_flags ^= SMazeCell::WallNorth;
					pRndNeigh->m_flags ^= SMazeCell::WallSouth;
				}
				break;
			case CMaze::east:
				{
					pCurrCell->m_flags ^= SMazeCell::WallEast;
					pRndNeigh->m_flags ^= SMazeCell::WallWest;
				}
				break;
			case CMaze::south:
				{
					pCurrCell->m_flags ^= SMazeCell::WallSouth;
					pRndNeigh->m_flags ^= SMazeCell::WallNorth;
				}
				break;
			case CMaze::west:
				{
					pCurrCell->m_flags ^= SMazeCell::WallWest;
					pRndNeigh->m_flags ^= SMazeCell::WallEast;
				}
				break;
			default:
				break;
			}
			// push CurrentCell location on the CellStack  
			m_stkCells.push(pCurrCell);
			// make the new cell CurrentCell  
			pCurrCell = pRndNeigh;
			// add 1 to VisitedCells
			++uiVisitedCells;
		}
		else
		{
			//pop the most recent cell entry off the CellStack and make it CurrentCell
			assert(!m_stkCells.empty());
			pCurrCell = m_stkCells.top();
			m_stkCells.pop();
		}
	}
}

bool CMaze::getNeighWithIntactWall(const MazeCellPtr& pCenterCell, MazeCellPtr& pResultCell, CMaze::eDirection dir)
{
	unsigned int uiIdx = 0;

	switch (dir)
	{
	case CMaze::north:
		{
			if (pCenterCell->m_uiY == 0)
				return false;
			uiIdx = (pCenterCell->m_uiY - 1) * m_uiSizeX + (pCenterCell->m_uiX);
		}
		break;
	case CMaze::east:
		{
			if (pCenterCell->m_uiX == (m_uiSizeX - 1))
				return false;
			uiIdx = (pCenterCell->m_uiY) * m_uiSizeX + (pCenterCell->m_uiX + 1);
		}
		break;
	case CMaze::south:
		{
			if (pCenterCell->m_uiY == (m_uiSizeY - 1))
				return false;
			uiIdx = (pCenterCell->m_uiY + 1) * m_uiSizeX + (pCenterCell->m_uiX);
		}
		break;
	case CMaze::west:
		{
			if (pCenterCell->m_uiX == 0)
				return false;
			uiIdx = (pCenterCell->m_uiY) * m_uiSizeX + (pCenterCell->m_uiX - 1);
		}
		break;
	default:
		return false;
	}
	if ((m_vecCells[uiIdx]->m_flags & SMazeCell::Walls) != SMazeCell::Walls)
		return false;
	pResultCell = m_vecCells[uiIdx];
	return true;
}


void CMaze::reset()
{
	reset(0, 0);
}

void CMaze::reset(unsigned int uiSizeX, unsigned int uiSizeY)
{
	// clear cells
	for (std::vector<MazeCellPtr>::iterator ite = m_vecCells.begin();
		ite != m_vecCells.end(); ++ite)
	{
		(*ite).reset();
	}
	m_vecCells.resize(0);
	// create new maze
	m_uiSizeX = uiSizeX;
	m_uiSizeY = uiSizeY;
	m_vecCells.resize(uiSizeX * uiSizeY);

	for (unsigned int j = 0; j < m_uiSizeY; ++j)
	{
		for (unsigned int i = 0; i < m_uiSizeX; ++i)
		{
			m_vecCells[j * uiSizeX + i] = MazeCellPtr(new SMazeCell(i, j));
		}
	}
}

